﻿#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
//[978. 最长湍流子数组](https://leetcode.cn/problems/longest-turbulent-subarray/)
class Solution
{
public:
	//动态规划：
	//由分析可知：只有一个状态解决不了这道题目
	//即f[i]表示：以i位置元素为结尾的所有子数组中，最后呈现“上升”状态下的最长湍流子数组
	//即g[i]表示：以i位置元素为结尾的所有子数组中，最后呈现“下降”状态下的最长湍流子数组
	//f和g还分为两种情况
	//f: arr[i-1] >= arr[i] 为1
	//f: arr[i-1] < arr[i]  为g[i-1] + 1
	//g: arr[i-1] <= arr[i] 为1
	//g: arr[i-1] >  arr[i] 为f[i-1] + 1

	int maxTurbulenceSize(vector<int>& arr)
	{
		int n = arr.size();
		if (n == 1) return 1;
		//建立dp表
		vector<int>f(n, 1);
		vector<int>g(n, 1);
		int ret = 0;
		for (int i = 1; i < n; i++)
		{
			if (arr[i - 1] > arr[i]) g[i] = f[i - 1] + 1;
			else if (arr[i - 1] < arr[i]) f[i] = g[i - 1] + 1;
			ret = max(ret, max(g[i], f[i]));
		}
		return ret;
	}
};
//[139. 单词拆分] (https://leetcode.cn/problems/word-break/)
class Solution
{
public:
	//状态转移方程
	//对于 dp[i] ，为了确定当前的字符串能否由字典⾥⾯的单词构成，根据最后⼀个单词的起始位
	//置 j ，我们可以将其分解为前后两部分：
	//前⾯⼀部分 [0, j - 1] 区间的字符串；
	//ii. 后⾯⼀部分 [j, i] 区间的字符串
	//其中前⾯部分我们可以在 dp[j - 1] 中找到答案，后⾯部分的⼦串可以在字典⾥⾯找到。
	//因此，我们得出⼀个结论：当我们在从 0 ~ i 枚举 j 的时候，只要 dp[j - 1] = true
	//并且后⾯部分的⼦串 s.substr(j, i - j + 1) 能够在字典中找到，那么 dp[i] = true 。
	bool wordBreak(string s, vector<string>& wordDict)
	{
		//优化：将每个字符串进行哈希映射
		unordered_set<string>hash;
		for (auto& s : wordDict)
		{
			hash.insert(s);
		}

		//建立dp表
		int n = s.size();
		vector<bool>dp(n + 1);
		//初始化
		dp[0] = true;//为了后续的填表结果正确
		s = ' ' + s;

		for (int i = 1; i <= n; i++)
		{
			for (int j = i; j >= 1; j--)
			{
				if (dp[j - 1] && hash.count(s.substr(j, i - j + 1)))
				{
					dp[i] = true;
					break;
				}
			}
		}
		return dp[n];
	}
};